package cn.edu.thu.thss.algorithm.mathematics;

import java.util.Arrays;

/**
 * 数论方面的基本工具类
 * @author EricPai
 */
public class NumberUtils {
	
	/**
	 * 找到从0~n的所有素数
	 * @param 最大整数n
	 * @return 是否为素数的结果
	 */
	public boolean[] findAllPrimes(int n) {
		boolean[] prime = null;
		if (n == 0) {
			prime = new boolean[]{false};
		} else if (n >= 1) {
			prime = new boolean[n + 1];
			Arrays.fill(prime, true);
			prime[0] = false;
			prime[1] = false;
			int m = (int)(Math.sqrt(n));
			for (int i = 2; i <= m; i++) {
				if (prime[i]) {
					for (int k = i * i; k <= n; k += i) {
						prime[k] = false;
					}
				}	
			}
		}
		return prime;
	}

	/**
	 * 判断整数n是否为素数
	 * @param 要判断的整数n
	 * @return true为素数。false不为素数
	 */
	public boolean isPrime(int n) {
		if (n <= 1) {
			return false;
		}
			
		if (n == 2) {
			return true;
		}
			
		if (n % 2 == 0) {
			return false;
		}
		
		int m = (int)(Math.sqrt(n));
		for (int i = 3; i <= m; i += 2) {
			if (n % i == 0) {
				return false;
			}
		}	
		return true;
	}
	
	/**
	 * 找到两个整数的最大公约数
	 * @param a 第一个整数
	 * @param b 第二个整数
	 * @return a和b的最大公约数
	 */
	public int findGCD(int a, int b)
	{
	   if (b==0) return a;
	   return findGCD(b,a%b);
	}
	
	/**
	 * 找到两个整数的最小公倍数
	 * @param a 第一个整数
	 * @param b 第二个整数
	 * @return a和b的最小公倍数
	 */
	public int findLCM(int a, int b)
	{
	   int gcd = findGCD(a,b);
	   return gcd == 0 ? 0 : Math.abs(b * a / gcd);
	}
}
